package cn.datastruct.EightTree;

import com.sun.source.tree.Tree;

import java.util.Stack;

/**
 * 思路：
 * 1.大于当前节点的值就往右边放
 * 2.小于等于就往左边节点放
 * 3.递归实现一二直到节点指向null
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) throws Exception {
        int[] arr = {7, 3, 10, 1, 5, 9, 12, 2};
        int length = arr.length;
        BinarySortTree BST = new BinarySortTree();
        for (int i = 0; i < length; i++) {
            BST.add(new TreeNode(arr[i]));
        }
        BST.delTreeNode(7);
        System.out.println();
        BST.infixOrder();
    }
}

//二叉排序树
class BinarySortTree {
    TreeNode root;//根节点

    //添加节点
    public void add(TreeNode node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

    //删除节点

    /**
     * 思路：
     * 一、目标节点为叶子节点，直接targetNode = null
     * 二、目标节点有一个子节点
     * 1.左子节点
     * 1.1，parent.left = targetNode.left
     * 1.2.parent.left = targetNode.right
     * 2.左子节点
     * 2.1，parent.left = targetNode.left
     * 2.2.parent.left = targetNode.right
     * <p>
     * 三、目标节点有两个字节点
     * 1.1.找出右子树最小的一个节点或左子树最大的一个节点
     * 2.1.用一个临时变量temp保存最小的那个节点
     * 3.1.删除最小的节点
     * 4.1.temp赋给要删除的节点
     */
    public int delTreeNodeMin(TreeNode node) throws Exception {
        TreeNode target = node;
        //往左边找最小的数
        while (target.left != null) {
            target = target.left;
        }
        int temp =  target.val;//最小的数字
        //删除该节点
        this.delTreeNode(node, target.val);
        return target.val;
    }

    public void delTreeNode(int value) throws Exception {
        this.delTreeNode(this.root, value);
    }

    public void delTreeNode(TreeNode node, int value) throws Exception {

        //如果目标节点为第一个
        if (this.root.left == null && this.root.right == null) {
            this.root = null;
            return;
        }
        TreeNode targetNode = SearchNode(node, value);//找到目标节点
        TreeNode parent = SearchParent(node, value);//找打目标节点的父节点
        //targetNode为叶子节点
        if (targetNode.right == null && targetNode.left == null) {
            ////判断是parent节点的左子节点还是右子节点
            if (parent.left == targetNode) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (targetNode.right != null && targetNode.left != null) {//目标节点有两个子树
            int temp = delTreeNodeMin(targetNode.right);//最小值
            targetNode.val = temp;
        } else {//只有一个子树
            //判断是左子树还是右子树
            if (targetNode.left != null) {
                if (parent.left == targetNode) {
                    parent.left = targetNode.left;
                } else {
                    parent.right = targetNode.left;
                }
            } else {
                if (parent.left == targetNode) {
                    parent.left = targetNode.right;
                } else {
                    parent.right = targetNode.right;
                }
            }
        }
    }

    //查找要删除的节点
    public TreeNode SearchNode(int value) throws Exception {
        return this.SearchNode(this.root, value);
    }

    public TreeNode SearchNode(TreeNode node, int value) throws Exception {
        //开始查找
        if (node.val == value) {//找到节点
            return node;
        } else if (node.val > value) {//左子树寻找
            if (node.left == null) {
                return null;
            } else {
                return SearchNode(node.left, value);//左子树遍历
            }
        } else if (node.val < value) {//只剩下右子树
            if (node.right == null) {
                return null;
            } else {
                return SearchNode(node.right, value);//左子树遍历
            }
        }
        //不存在节点就报错
        throw new Exception();
    }

    //寻找要删除节点的父节点
    public TreeNode SearchParent(int value) {
        return this.SearchParent(this.root, value);
    }

    public TreeNode SearchParent(TreeNode node, int value) {//如果是第一个节点怎么处理
        if ((node.left != null && node.left.val == value) || (node.right != null && node.right.val == value)) {//找到该节点
            return node;
        } else if (node.left != null && node.val > value) {//左字节不为空且小于value
            return SearchParent(node.left, value);
        } else if (node.right != null && node.val <= value) {//右字节不为空且大于等于value
            return SearchParent(node.right, value);
        }
        //第一个节点
        return null;
    }

    //中序遍历重写
    public void infixOrder() {
        this.infixOrder(this.root);
    }

    //中序遍历
    public void infixOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        //遍历左子树
        if (node.left != null) {
            this.infixOrder(node.left);
        }

        System.out.printf("%d\t", node.val);

        //遍历右子树
        if (node.right != null) {
            this.infixOrder(node.right);
        }
    }

    //前序排列栈实现
    public void preOrder() throws Exception {
        this.preOrder(this.root);
    }

    public void preOrder(TreeNode node) throws Exception {
        //树为空返回
        if (node == null)
            throw new Exception("树为空");
        //定义哥栈来保存节点
        Stack<TreeNode> stack = new Stack<>();

        //当栈为空或当前节点为null退出
        while (node != null || !stack.isEmpty()) {
            //遍历左子节点
            while (node != null) {
                //保存当前节点
                System.out.printf("%d\t", node.val);
                stack.push(node);
                node = node.left;
            }
            //指向右子节点
            node = stack.pop().right;
        }
    }

}

//实现一个节点
class TreeNode {
    //成员变量
    int val;//数值
    TreeNode left;//指向左节点
    TreeNode right;//指向右节点

    //构造函数
    public TreeNode(int val) {
        this.val = val;
    }

    //添加节点
    public void add(TreeNode node) {
        if (node == null) {//添加空节点
            return;
        }
        if (node.val < this.val) {//比较当前节点
            if (this.left == null) {//如果当前节点的左子树为空则直接添加
                this.left = node;
            } else {//如果当前节点的左子树不为空则继续深入
                this.left.add(node);
            }
        } else {
            if (this.right == null) {//如果当前节点的右子树为空则直接添加
                this.right = node;
            } else {//如果当前节点的右子树不为空则继续深入
                this.right.add(node);
            }

        }
    }
}
